Internet is formed of a plurality of networks connected to each other, wherein each of the constituent networks maintains its identity. Each network supports communication among devices connected to the networks, and the networks in their turn are connected by routers. Thus, Internet can be considered to comprise a mass of routers interconnected by links. Communication among nodes (routers) on Internet takes place using an Internet protocol, commonly known as IP. IP data grams (data packets) are transmitted over links from one router to the next one on their ways towards the final destinations. In each router a forwarding decision is performed on incoming data grams to determine the data grams next-hop router.
A routing or forwarding decision is normally performed by a lookup procedure in a forwarding data structure such as a routing table. Thus, IP routers do a routing lookup in the routing table to obtain next-hop information about where to forward the IP data grams on their path toward their destinations. A routing lookup operation on an incoming datagram requires the router to find the most specific path for the datagram. This means that the router has to solve the so-called longest prefix matching problem which is the problem of finding the next-hop information (or index) associated with the longest address prefix matching the incoming data grams destination address in the set of arbitrary length (i.e. between 3 and 65 bits) prefixes constituting the routing table.
To speed up the forwarding decisions, many IP router designs of today use a caching technique, wherein the most recently or most frequently looked up destination addresses and the corresponding routing lookup results are kept in a route cache. This method works quite well for routers near the edges of the network, i.e. so called small office and home office (SOHO) routers having small routing tables, low traffic loads, and high locality of accesses in the routing table.
Another method of speeding up the routers is to exploit the fact that the frequency of routing table updates, resulting from topology changes in the network etc., is extremely low compared to the frequency of routing lookups. This makes it feasible to store the relevant information from the routing table in a more efficient forwarding table optimized for supporting fast lookups.
In this context, a forwarding table is an efficient representation of a routing table and a routing table is a dynamic set of address prefixes. Each prefix is associated with next hop information, i.e. information about how to forward an outgoing packet and the rules of the game state that the next-hop information associated with the longest matching prefix of the destination address (of the packet) must be used. When changes to the routing table occur, the forwarding table is partially or completely rebuilt.
An example of a forwarding data structure is a so-called “static block tree”, which is a comparison based data structure for representing w-bit non-negative integers with d-bit data and supporting extended search in time proportional to the logarithm with base B, where B-1 is the number of integers that can stored in one memory block, of the number of integers stored. Typically, it is a static data structure which supports efficient extended search with minimum storage overhead. The static block tree data structure has previously been described in the Swedish patent 0200153-5, which refers to a method and system for fast IP routing lookup using forwarding tables with guaranteed compression ratio and lookup performance where it is referred to as a Dynamic Layered Tree and also in M. Sundström and Lars-Åke Larzon, High-Performance Longest Prefix Matching supporting High-Speed Incremental Updates and Guaranteed Compression, IEEE INFOCOMM, Miami Fla., USA, 2005.
A basic block tree, for instance in the form of a dynamic layered tree, consists of at least one leaf and possibly a number of nodes if the height is larger than one. The height corresponds to the number of memory accesses required for looking up the largest stored non-negative integer smaller than or equal to the query key. This kind of lookup operation is referred to as extended search.
The problem solved by a basic block tree is to represent a partition, of a totally ordered universe U, consisting of n basic intervals. Since U is known, also minU and maxU are known. Therefore, it is sufficient to represent n−1 interval boundaries where each interval boundary is represented by an element which is a w-bit non-negative integer. The w-bit non-negative integer is referred to as the key and the corresponding d-bit data field as the data. In one memory block, we can store B elements and thus represent B+1 intervals. We call the resulting data structure a basic block tree of height 1. Each basic interval constitutes a subset of U. For each subset, we can recursively represent a partition consisting of B+1 intervals by using one additional memory block. By combining the original partition of U with the B+1 sub-partitions, we obtain a block tree of height 2 representing (B+1)2 basic intervals. Assuming that pointers to sub-structures can be encoded implicitly, it is possibly to recursively construct a block tree of arbitrary height t for representing up to (B+1)t basic intervals.
A block tree of height t that represents exactly (B+1)t intervals is said to be complete. Otherwise it is partial. The need for pointers is avoided by storing a block tree in a consecutive array of memory blocks. To store a block tree of height t, first the root block is stored in the first location. This is followed by up to B+1 recursively stored complete block trees of height t−1 and possibly one recursively stored partial block tree of height t−1. No pointers are needed since the size s(t−1) of a complete block tree of height t−1 can be computed in advance. The root of sub-tree i is located i·s(t−1) memory blocks beyond the root block (assuming that the first sub-tree has index zero).
Typically, there are two major problems with basic block trees. The first problem is related to worst case storage cost. More precisely, the worst case amortized number of bits required for storing n keys and their corresponding data may be considerably larger than n·(w+d) in the worst case resulting in a worst case cost per key of much more than w+d bits which is optimal (at least in a sense). The second problem is related to incremental updates. A basic block tree is essentially static which means that the whole data structure must be rebuilt from scratch when a new key and data is inserted or deleted. As a result, the cost for updates is too high, i.e. at least in some applications, it takes too much time and computation, in particular if the block tree is large.
When comparing block trees with tries, for example t-level fixed stride tries, we observe a third problem with block trees namely the lookup cost. Whereas such a trie has a bounded lookup cost of t steps (or memory accesses), independently of the number of intervals, the lookup cost in a block tree grows logarithmically with the number of intervals. Another key aspect of the performance is the worst case storage costs per interval. Whereas the total storage cost in a block tree grows linearly with the number of intervals and could potentially be reduced to only w+d bits per interval using the present invention, there is an explosive growth of the worst case storage cost of a fixed stride trie if t is considerably less that w, which is typically the case since it would not make any sense otherwise to bound the lookup cost. Another problem with fixed stride tries is the high worst case cost for incremental updates. If the data structure is stored in a packed memory area without any efficient mechanisms to move around trie nodes and to manage memory allocation and deallocation, a single update may potentially require that the whole data structure is rebuilt from scratch as with a basic block tree.